//
// Created by 莫道 on 2018/11/8.
//

#ifndef TEST_BINARYTREE_LINKEDSTACK_H
#define TEST_BINARYTREE_LINKEDSTACK_H
#include <iostream>
#include <cassert>
using namespace std;

template <typename T>struct StackNode{
    T data;
    StackNode<T> *link;
    StackNode(T d = 0, StackNode<T> *next = NULL):link(next),data(d){}
};

template <typename T>class LinkedStack{
private:
    StackNode<T> *top;
public:
    LinkedStack():top(NULL){}//无头结点
    ~LinkedStack(){
        makeEmpty();
    }
    void Push(const T &x);
    bool Pop(T &x);
    bool getTop(T &x)const;
    int getSize()const;
    bool IsEmpty()const{
        return top == NULL;
    }
    bool IsFull()const{
        return false;
    }
    void makeEmpty();
    friend ostream& operator << (ostream &os, LinkedStack<T> &s)	{
        os << "Stack Size: " << s.getSize() << endl;
        StackNode<T> *p = s.top;
        int i = 0;
        while (p){
            os << ++i << ": " << p->data << endl;
            p = p->link;
        }
        return os;
    }
};

template <typename T>void LinkedStack<T>::makeEmpty(){
    StackNode<T> *p;
    while (top){//最后top为NULL
        p = top;
        top = top->link;
        delete p;
    }
}

template <typename T>void LinkedStack<T>::Push(const T &x){
    top = new StackNode<T>(x, top);
    assert(top);
}

template <typename T>bool LinkedStack<T>::Pop(T &x){
    if (IsEmpty()){
        return false;
    }
    StackNode<T> *p = top;
    top = top->link;
    x = p->data;
    delete p;
    return true;
}

template <typename T>bool LinkedStack<T>::getTop(T &x)const{
    if (IsEmpty())	return false;
    x = top->data;
    return true;
}

template <typename T>int LinkedStack<T>::getSize()const{
    StackNode<T> *p = top;
    int k = 0;
    while (p){
        p = p->link;
        k++;
    }
    return k;
}
#endif //TEST_BINARYTREE_LINKEDSTACK_H
